package binaryTree.LayerOrderTraversal.review;


import java.util.*;

public class Traverse {


//    public List<Integer> preorderTraversal(TreeNode root) {
//        ArrayList<Integer> list = new ArrayList<>();
//        preOrderTraver(root,list);
//        return  list;
//    }
//    //递归实现遍历
//    public  void preOrderTraver(TreeNode root, ArrayList list){
//        if (root==null){
//            return;
//        }
//        preOrderTraver(root.left,list);
//        list.add(root.val);
//        preOrderTraver(root.right,list);
//    }


    public void preTraverse(TreeNode root, ArrayList<Integer> list) {
        if (root==null){
            return;
        }
        list.add(root.val);
        preTraverse(root.left, list);
        preTraverse(root.right, list);
    }

    public void inTraverse(TreeNode root, ArrayList<Integer> list) {
        if (root==null){
            return;
        }
        inTraverse(root.left, list);
        list.add(root.val);
        inTraverse(root.right, list);
    }

    public void postTraverse(TreeNode root, ArrayList<Integer> list) {
        if (root==null){
            return;
        }
        postTraverse(root.left, list);
        list.add(root.val);
        postTraverse(root.right, list);
    }


    public ArrayList<ArrayList<Integer>> levelTraverse(TreeNode root){
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        //  CKG TODO 2023/3/30: 　先来一个队列　 保存读取到的节点
//        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root!=null){
           queue.offer(root);
        }
        while (!queue.isEmpty()){
            int size = queue.size();
            //  CKG TODO 2023/3/30: 进行每一层的每个节点的遍历
            ArrayList<Integer> temp = new ArrayList<>();
            while (size>0){
                TreeNode cur = queue.poll();
                if (cur.left!=null){
                    queue.offer(cur.left);
                }
                if (cur.right!=null){
                    queue.offer(cur.right);
                }
                temp.add(cur.val);
                size--;
            }
            lists.add(temp);
        }
        return lists;
    }


    public ArrayList<ArrayList<Integer>> checkFun02(TreeNode node) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (node == null) return  null;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }
            lists.add((ArrayList<Integer>) itemList);
        }

        return lists;

    }
//    public List<List<Integer>> levelOrderBottom(binaryTree.LayerOrderTraversal.TreeNode root) {
////        二叉树的层序遍历，就是最后把result数组反转一下就可以了
//        List<List<Integer>> resList = new ArrayList<List<Integer>>();
//        LinkedList<binaryTree.LayerOrderTraversal.TreeNode> queue = new LinkedList<>();
//        if (root!=null){
//            queue.offer(root);
//        }
//        while (!queue.isEmpty()){
//            int size = queue.size();
//            ArrayList<Integer> temp = new ArrayList<>();
//            while (size>0){
//                binaryTree.LayerOrderTraversal.TreeNode node = queue.poll();
//                size--;
//                temp.add(node.val);
//
//                if (node.left!=null){
//                    queue.offer(node.left);
//                }
//                if (node.right!=null){
//                    queue.offer(node.right);
//                }
//            }
//            resList.add(temp);
//        }
//
//        Collections.reverse(resList);
//        return resList;
//    }
//



//
//    //同一版本　迭代实现前中后序遍历　　
//    //todo:无论是前中后序遍历　添加的顺序都是　都是与原本遍历顺序倒着进行添加　
//    public List<Integer> preorderTraversal1(binaryTree.LayerOrderTraversal.TreeNode root) {
//        List<Integer> result = new LinkedList<>();
//        Stack<binaryTree.LayerOrderTraversal.TreeNode> st = new Stack<>();
//        if (root != null) st.push(root);
//        while (!st.empty()) {
//            binaryTree.LayerOrderTraversal.TreeNode node = st.peek();
//            if (node != null) {
//                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
//                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
//                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
//                st.push(node);                          // 添加中节点
//                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
//
//            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
//                st.pop();           // 将空节点弹出
//                node = st.peek();    // 重新取出栈中元素
//                st.pop();
//                result.add(node.val); // 加入到结果集
//            }
//        }
//        return result;
//    }


    public static void main(String[] args) {

        TreeNode root = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(2);
        TreeNode treeNode4 = new TreeNode(6);
        root.left = treeNode1;
        root.right = treeNode3;
        treeNode1.left = treeNode2;
        treeNode3.right = treeNode4;

        Traverse traverse = new Traverse();
//        ArrayList<Integer> integers = new ArrayList<>();
//
//        traverse.preTraverse(root,integers);
//        for (int a:integers) {
//            System.out.println(a);
//        }
        ArrayList<ArrayList<Integer>> arrayLists = traverse.levelTraverse(root);
        for (ArrayList  a:
             arrayLists) {
            for (int i = 0; i <a.size() ; i++) {
                System.out.println(a.get(i));
            }
            }
        }





    }



